#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 2e5+10;

int s[N<<6],ls[N<<6],rs[N<<6],rt[N],a[N],n,m,nodenum,nd1[N],nd2[N],tot,tot1,tot2,b[N<<1],op[N],L[N],X[N],Y[N],R[N],K[N];

void update(int &y,int pos,int v,int l,int r){
	if(!y) y = ++nodenum; s[y] += v;
	if(l == r) return;
	int mid = l+r>>1;
	if(pos <= mid) update(ls[y],pos,v,l,mid); else update(rs[y],pos,v,mid+1,r);
}

void update(int pos,int num,int v){
	for(int i = pos;i <= n;i+=i&-i) update(rt[i],num,v,1,tot);
}

int query(int k,int l,int r){
	if(l == r) return l;
	int mid = l+r>>1;
	int sum = 0;
	for(int i = 1;i <= tot1;i++) sum -= s[ls[nd1[i]]];
	for(int i = 1;i <= tot2;i++) sum += s[ls[nd2[i]]];
	if(k <= sum) {
		for(int i = 1;i <= tot1;i++) nd1[i] = ls[nd1[i]];
		for(int i = 1;i <= tot2;i++) nd2[i] = ls[nd2[i]];
		return query(k,l,mid);
	}
	else {
		for(int i = 1;i <= tot1;i++) nd1[i] = rs[nd1[i]];
		for(int i = 1;i <= tot2;i++) nd2[i] = rs[nd2[i]];
		return query(k-sum,mid+1,r);
	}
}

int query_tot(int l,int r,int k){
	tot1 = tot2 = 0;
	for(int i = l-1;i;i-=i&-i) nd1[++tot1] = rt[i];
	for(int i = r;i;i-=i&-i) nd2[++tot2] = rt[i];
	return query(k,1,tot);
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,m = in;
	for(int i = 1;i <= n;i++) a[i] = in,b[++tot] = a[i];
	for(int i = 1;i <= m;i++){
		char ch = getchar(); while(!isalpha(ch)) ch = getchar();
		op[i] = ch == 'C';
		if(op[i] == 0) L[i] = in,R[i] = in,K[i] = in;
		else X[i] = in,Y[i] = in,b[++tot] = Y[i];
	}
	sort(b+1,b+tot+1); tot = unique(b+1,b+tot+1) - b - 1;
	for(int i = 1;i <= n;i++) {
		a[i] = lower_bound(b+1,b+tot+1,a[i]) - b;
		update(i,a[i],1);
	}
	for(int i = 1;i <= m;i++){
		if(op[i]){
			update(X[i],a[X[i]],-1);
			a[X[i]] = lower_bound(b+1,b+tot+1,Y[i]) - b;
			update(X[i],a[X[i]],1);
		}else{
			printf("%d\n",b[query_tot(L[i],R[i],K[i])]);
		}
	}
	return 0;
}

